GATE CSE 2021 SET-2
Q1.
Consider the following ANSI C code segment: z=x + 3 + y-> f1 + y-> f2; for (i = 0; i < 200; i = i + 2) { if (z > i) { p = p + x + 3; q = q + y-> f1; } else { p = p + y-> f2; q = q + x + 3; } }Assume that the variable y points to a struct (allocated on the heap) containing two fields f1 and f2, and the local variables x, y, z, p, q, and i are allotted registers. Common sub-expression elimination (CSE) optimization is applied on the code. The number of addition and the dereference operations (of the form y -> f1 or y -> f2) in the optimized code, respectively, are:Q2.
Consider the following ANSI C program. #include < stdio.h > int main( ) { int arr[4][5]; int i, j; for (i=0; i < 4; i++) { for (j=0; j < 5; j++) { arr[i][j] = 10 * i + j; } } printf("%d", *(arr[1]+9)); return 0; } What is the output of the above program?Q3.
What is the worst-case number of arithmetic operations performed by recursive binary search on a sorted array of size n?Q4.
Consider a set-associative cache of size 2KB (1KB=2^{10} bytes) with cache block size of 64 bytes. Assume that the cache is byte-addressable and a 32 -bit address is used for accessing the cache. If the width of the tag field is 22 bits, the associativity of the cache is ______Q5.
Assume a two-level inclusive cache hierarchy, L1 and L2, where L2 is the larger of the two. Consider the following statements. S1: Read misses in a write through L1 cache do not result in writebacks of dirty lines to the L2 S2: Write allocate policy must be used in conjunction with write through caches and no-write allocate policy is used with writeback caches. Which of the following statements is correct?Q6.
Suppose that f: \mathbb{R} \rightarrow \mathbb{R} is a continuous function on the interval [-3,3] and a differentiable function in the interval (-3,3) such that for every x in the interval, f'(x) \leq 2. If f(-3) =7, then f(3) is at most __________Q7.
For two n-dimensional real vectors P and Q, the operation s(P,Q) is defined as follows: s(P,Q) = \displaystyle \sum_{i=1}^n (P[i] \cdot Q[i]) Let \mathcal{L} be a set of 10-dimensional non-zero real vectors such that for every pair of distinct vectors P,Q \in \mathcal{L}, s(P,Q)=0. What is the maximum cardinality possible for the set \mathcal{L}?Q8.
Consider a complete binary tree with 7 nodes. Let A denote the set of first 3 elements obtained by performing Breadth-First Search (BFS) starting from the root. Let B denote the set of first 3 elements obtained by performing Depth-First Search (DFS) starting from the root. The value of |A-B| is _____________Q9.
For a string w, we define w^R to be the reverse of w. For example, if w=01101 then w^R=10110. Which of the following languages is/are context-free?[MSQ]Q10.
Let L_1 be a regular language and L_2 be a context-free language. Which of the following languages is/are context-free?[MSQ]